We provide a formal proof on the following properties
- If a heuristic is consistent, it must be admissible. We also give an example heuristic which is admissible, but not consistent.
A*of graph search is NOT optimal with admissible heuristic.
For the second property, the course book only says that “A* of graph search is optimal with consistent heuristic”. Some students are wondering whether the conclusion that
A* of graph search is optimal with admissible heuristic
is true or not (see the page). Here, we show this conclusion is wrong. The key point is that the frontier set in graph search include both the visited and unvisited nodes.
Please check the following pdf.
(Thanks to Xingcheng Ruan.)